package greedy

// 这道题非常类似 402号算法题了。
// 移掉k位数字，保证剩下的最小。
// 这里是移掉重复的位, 保证最小（字典序）
// abcdefg..xyz 正序排列就是最小的了，类似于123456789排列。
// 维护递增栈，两个map用来判断，当前元素是否在栈中，是否在队列中
func removeDuplicateLetters(s string) string {
	stack := make([]byte, 0)
	// stack 用来快速判断，一个元素是否在栈中
	// sCnt 用来记录所有元素，当前遍历位置后面还有哪些元素
	stackCnt := make(map[byte]int, 0)
	sCnt := make(map[byte]int, 0)
	for i := 0; i < len(s); i++ {
		sCnt[s[i]] = sCnt[s[i]] + 1
	}
	for i := 0; i < len(s); i++ {
		// 遍历过的，从计数中删除，统计的是 遍历后还有哪些元素
		sCnt[s[i]] -= 1
		// 4. 如果当前元素已经在栈里面了，那就跳过。因为递增栈，删除开头的，那么只会导致字典序更大。
		// 这里千万不要晕！！ 因为给人的感觉是，只要前面的，后面一重复出现就跳过，好像没有选择一样
		// 其实因为是单调栈，如果当前元素再栈中，那么它 "没有被后面的大于它的元素淘汰"，所以保持了递增性。符合小元素在前。应当跳过当前位置，啥也不干
		if stackCnt[s[i]] > 0 {
			continue
		}
		// 1. 空栈直接添加， 或者当前元素大于栈顶 直接添加
		if len(stack) == 0 || s[i] > stack[len(stack)-1] {
			stackCnt[s[i]] = stackCnt[s[i]] + 1
			stack = append(stack, s[i])
			continue
		}
		// 2. 当前元素等于栈顶元素，啥也不干
		if s[i] == stack[len(stack)-1] {
			continue
		}
		// 3. 当前元素小于栈顶元素
		for len(stack) > 0 && s[i] < stack[len(stack)-1] {
			// 如果后面还有, 删除当前栈顶元素，否则退出
			c := stack[len(stack)-1]
			if sCnt[c] > 0 {
				stack = stack[:len(stack)-1]
				stackCnt[c] = stackCnt[c] - 1
			} else {
				break
			}
		}
		// 清除掉栈顶大于的元素（可能不需要清除），将当前元素添加进去
		stack = append(stack, s[i])
		stackCnt[s[i]] = stackCnt[s[i]] + 1
	}
	return string(stack)
}
